/*
 * @lc app=leetcode.cn id=464 lang=javascript
 *
 * [464] 我能赢吗
 */

// @lc code=start
/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */

var dfs = function(mask, n , desiredTotal, cache){
  if(cache[mask]) return cache[mask];
  for (let i = 1; i <= n; i++) {
    // mask 从右往左第i位是否为 1
    if(mask & (1 << i)) continue;

    // 判断前一次抓牌（对手抓牌）是否为输
                            // 将mask 从右往左第i位置为 1
    if(i >= desiredTotal || !dfs(mask | (1 << i), n, desiredTotal - i, cache)){
      cache[mask] = true;
      return true;
    }
  }
  cache[mask] = false;
  return false;
}
var canIWin = function(maxChoosableInteger, desiredTotal) {
  let n = maxChoosableInteger;
  // 记录已经计算过的选择顺所序返回的结果
  let cache = {};
  // mask 二进制表示记录备选过的数字， 0 未选， 1已选
  let mask = 0;
  // 总和小于目标和
  if(n * (n + 1)/2 < desiredTotal) return false;
  return dfs(mask, n , desiredTotal, cache);
};
// @lc code=end

